/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii
   @Language: C++
   @Datetime: 19-11-21 11:47
   */

// Time O(logn), Space O(1)
// The original array must sorted in ascending order
class Solution {
public:
	int findMin(vector<int>& nums) {
		int i=0;
		for(int k, j=nums.size()-1; i<j;){
			k=(i+j)/2;
			if(nums[k]>nums[j]) i=k+1;
			else if(nums[k]<nums[i]) j=k;
			else --j;
		}
		return nums[i];
	}
};

